/****************************************	
 *  Submitted by:				        *
 *  Michael Fildstein, ID: 309161594    *
 *	Tomer Ben Rachel, ID: 021982475	 	*
 *       								*
 ***************************************/
/*
This program attempts to solve a series of linear equations that are represented using a matrix.
In the first part of this program, using the function printMatrix, we print the linear equations onto the screen
Then, using the function checkSolution, we check to see if a given solution solves the series of the linear equations.
Finally, through the function solveEquations, we check to see if a given series of linear equations have either:
1.One solution and we return that solution
2.No solution at all and we return null
3.Infinite solutions and we return one solution
*/





public class LinearEquations {

	public static void main(String[] args) {
		double[][] adMatrix = {{2,3,0,8},{0,1,4,14},{2,0,1,5}};
		double [][] testMatrix = {{2,3,5,8,17},{3,5,4,19,25},{6,9,11,18,-30}};			//for test purposes
		double [][] testMatrix2 = {{0,3,5,8,17},{0,5,4,19,25},{0,9,11,18,-30}};			//for test purposes
		double [][] testMatrix3 = {{1,1,10}, {1,1,20}};
		double [][] testMatrix4 = {{2,3,0,8,15},{0,1,4,14},{2,0,1,5}};
		double [][] testMatrix5 = {{2,3,0,8,15},{0,1,4,14},{2,0,1,5}};
		printMatrix(adMatrix);
		//should result in the following output:
		/*
		+ 2.0 X0 + 3.0 X1 = 8.0
		+ 1.0 X1 + 4.0 X2 = 14.0
		+ 2.0 X0 + 1.0 X2 = 5.0
		 */
		
		System.out.println(checkSolution(adMatrix, new double[]{1,2,3})); //should be true
		double[] adSolution = solveEquations(adMatrix);
		double [] solution2 = solveEquations(testMatrix);	//for test purposes
		double [] solution3 = solveEquations(testMatrix2);	//for test purposes
		double [] solution4 = solveEquations(testMatrix4);  //for test purposes
		double [] solution5 = solveEquations(testMatrix5);  //for test purposes

		System.out.println(solveEquations(testMatrix3));
		System.out.println(checkSolution(testMatrix, solution2));			//for test purposes
		System.out.println(checkSolution(testMatrix2, solution3));			//for test purposes
		System.out.println(checkSolution(testMatrix4, solution4));			//for test purposes
		System.out.println(checkSolution(testMatrix5, solution5));			//for test purposes
		for( int i = 0 ; i < adSolution.length ; i++ )
			System.out.print(adSolution[i] + ",");
		System.out.println(" ");
		for( int i = 0 ; i < solution2.length ; i++ )
			System.out.print(solution2[i] + ",");
		System.out.println(" ");
		for( int i = 0 ; i < solution3.length ; i++ )
			System.out.print(solution3[i] + ",");
		System.out.println(" ");

	}


//The function checkInput checks to see if the input for the code is correct. Meaning, not null, an array of negative length..
//Returns false if the input is incorrect. True if the input is correct

   public static boolean checkInput(double[][] adMatrix){
    boolean ans=true;
    if(adMatrix==null || adMatrix.length<1){
                ans=false;
                
	}else{
		if(ans)
			{for(int i=0;i<adMatrix.length && ans;i++){
				if(adMatrix[i]==null || adMatrix[i].length<2){
				   ans=false;
				}   
			}
		}
	}	
    if(!ans){
      System.out.println("Wrong Input!");
      }
   return ans;
		
}	






	//The function printMatrix prints the system of linear equations
	public static void printMatrix(double[][] adMatrix) {
		String matrix = new String();
		if(checkInput(adMatrix)){
			for (int j = 0 ; j < adMatrix.length ; j++){
				for (int i = 0 ; i < adMatrix.length  ; i++){
					if (adMatrix[j][i] > 0.0){	//If the number is positive
					  matrix = matrix + "+ " + adMatrix[j][i] + " X"+ i + " ";
					  }
					if (adMatrix[j][i] < 0.0){	//If the number is negative
					  matrix = matrix + "- " + Math.abs(adMatrix[j][i]) + " X"+ i + " ";
					  }	
				}
			System.out.println(matrix + "= " + adMatrix[j][adMatrix[j].length - 1] );
			matrix = "";
					
		     }
			 
		}     
	}
	
	public static void printMatrix2(double[][] adMatrix) {					//only for testing the dirug. 
		System.out.println(" ");
		String matrix = new String();
		
		for (int j = 0 ; j < adMatrix.length ; j++){
			for (int i = 0 ; i < adMatrix[j].length - 1  ; i++){
				if (adMatrix[j][i] > 0.0){
					matrix = matrix + "+ " + adMatrix[j][i] + " X"+ i + " ";
				}
				if (adMatrix[j][i] < 0.0){
					matrix = matrix + "- " + Math.abs(adMatrix[j][i])  + " X"+ i + " ";
				}
				if (adMatrix[j][i] == 0.0){
					matrix = matrix + "+ " + adMatrix[j][i] + " X"+ i + " ";
				}	
			}
			System.out.println(matrix + "= " + adMatrix[j][adMatrix[j].length - 1] );
			matrix = "";
					
		}
	}

	//The function checkSolution checks if the given solution to the system of linear equations is valid
  //And returns true if it is, otherwise, false
	public static boolean checkSolution(double[][] adMatrix, double[] adSolution){			
		boolean ans = true;
	    if(checkInput(adMatrix)){  
	        double test = 0.0;
	        for (int i = 0 ; i < adMatrix.length && ans ; i++){					//tests a given solution to linear equations
				for (int j = 0 ; j < adMatrix[i].length - 1 ; j++){
					test = test + adMatrix[i][j] * adSolution[j];
	            }
				ans = ((test >= (adMatrix[i][adMatrix[i].length - 1]) - 0.000000000000002 ) || (test <= (adMatrix[i][adMatrix[i].length - 1]) + 0.000000000000002 ));
				test = 0.0;  
	        }
	      }     
		return ans;	
	}
	
	
	
	// This function checks if all the Rows in the Matrix are in the same length.
	// Returns true if they are , and False if they are not.	
	public static boolean matrixRowsSameLength (double[][] adMatrix){
		boolean ans = true;
		for (int i = 0 ; i < adMatrix.length && ans  ; i ++){
			for (int j = i ; j < adMatrix.length - 1 && ans ; j++){
				if (adMatrix[i].length != adMatrix[j].length ){
					ans = false;
				}
			}
		}
		return ans;
	}
	
	//The function longestRow checks and returns the longest Row of a given Matrix.
	public static int longestRow (double [][] adMatrix){
		int ans = 0; 
		for (int i = 0 ; i < adMatrix.length ; i++){
			if (adMatrix[i].length >= ans){
				ans = adMatrix[i].length;
			}
        }
		return ans;
	}

	
	//The function matrixRowEqualizer makes all the rows in the matrix equal by adding zeros in the missing places
  //It returns the changed matrix
	public static double[][] matrixRowEqualizer (double [][] adMatrix){
		int longestRow = longestRow(adMatrix);
		double [][] ans = new double[adMatrix.length][longestRow];
		for (int i = 0 ; i < adMatrix.length ; i++){
			for (int j = 0 ; j < adMatrix[i].length - 1 ; j++){
				ans[i][j] = adMatrix[i][j];
            }
		ans[i][ans[i].length - 1] = adMatrix[i][adMatrix[i].length - 1]; 
        }
		return ans;
	}
	
	
	//The function swapRows swaps two rows in a matrix
	public static void swapRows (double[][] adMatrix , int rowA , int rowB){	//swaps two rows in a matrix
		double[] tempRow = new double[adMatrix[rowA].length];
		tempRow = adMatrix[rowA];
		adMatrix[rowA] = adMatrix[rowB];
		adMatrix[rowA] = tempRow;
	}
	
	//The function findNonZeroRow finds a row which doesn't have a zero in a given column
	//and returns the index of that row
	public static int findNonZeroRow (double [][] adMatrix , int column ,int row){   //finds a row number which doesn't have a zero in a givem column.
		int ans = -1;
		boolean found = false;
		for (int i = row ; i < adMatrix.length && !found ; i++ ){
			if (adMatrix[i][column] != 0){
				ans = i;
				found = true;
			}
        }
		return ans;
	}
	
   
	//The function divideRow divides a row by the constant we found earlier
	//and returns that row after the division
	public static double[] divideRow (double[][] adMatrix ,int rowNumber , double constant){ //divides a row by the constant.
		double [] newRow = new double [adMatrix[rowNumber].length];
		for (int i = 0 ; i < adMatrix[rowNumber].length ; i++){
			newRow[i] = adMatrix[rowNumber][i] / constant;
	    }
		return newRow;
	}
	
	//The function multiplyRow multiplies a row by the constant we found earlier
	//and returns that row after the multiplication.
	public static double[] multiplyRow (double[][] adMatrix ,int rowNumber , double constant){ //multiply a row by the constant.
		double [] newRow = new double [adMatrix[rowNumber].length];
		for (int i = 0 ; i < adMatrix[rowNumber].length ; i++){
			newRow[i] = adMatrix[rowNumber][i] * constant;
		}
		return newRow;
	}
	
	//The function substractRow subtracts Row B from Row A(rowA-rowB)
	//and returns the row after the subtraction
	public static double[] substractRow (double[] rowA , double[] rowB){ 
		double [] newRow;
		newRow = new double[rowA.length];
		for (int i = 0 ; i < rowB.length ; i++){
			newRow[i] = rowA[i] - rowB[i];
		}
		return newRow;
    }
	
	
	
	
	
	//The function upperTraingularMatrix2 rates the Matrix to an upperTraingularMatrix,  where all the numbers above the diagnol are zeros
  // 
	public static int[] uperTraingularMatrix2 (double [][] adMatrix){    
	    int row = 0;
		int column = 0;
		int rowWithNoZero = -1;
		int[] zeroColumn = new int[adMatrix[0].length];
		
		while (row < adMatrix.length){
			rowWithNoZero = findNonZeroRow(adMatrix, column , row);
				if (rowWithNoZero != -1){															//in case our column is not all zeros.
					swapRows(adMatrix, rowWithNoZero, row);
					adMatrix[row] = divideRow(adMatrix, row, adMatrix[row][column]);
					for ( int i = row + 1; i < adMatrix.length ; i++){
						adMatrix[i] = substractRow(adMatrix[i], multiplyRow(adMatrix, row, adMatrix[i][column])) ;
					}
				}else{   																		//in case our column IS all zeros.
					zeroColumn[column] = 1;
					column = column + 1;
					rowWithNoZero = findNonZeroRow(adMatrix, column , row);
					if (rowWithNoZero != -1){
						swapRows(adMatrix, rowWithNoZero, row);
						adMatrix[row] = divideRow(adMatrix, row, adMatrix[row][column]);
						for ( int i = row + 1; i < adMatrix.length ; i++){
							adMatrix[i] = substractRow(adMatrix[i], multiplyRow(adMatrix, row, adMatrix[i][column])) ;
	                    }
	                }
	            }	
			//printMatrix2(adMatrix);		//VERY IMPORTANT !!!!! SHOULD NOT BE IN THE FINAL VERSION !!!! ONLY FOR TESTING !!!
		row = row + 1;
		column = column + 1 ;
		}
		return zeroColumn;
  }
	

	//The function dirugMatrix gets an UpperTriangular matrix as an input and completes the dirug process
	public static void dirugMatrix (double [][] adMatrix){
		int row = adMatrix.length - 1;
		int column = -1;
		boolean movilFound = false;
		for (int i = 0 ; i < adMatrix[row].length - 1 && !movilFound ; i++){
			if (adMatrix[row][i] == 1){
				column = i;
				movilFound = true;
			}
        }
		while (row >= 0){
      		for (int i = row - 1 ;i >= 0 ; i--){
				adMatrix[i] = substractRow(adMatrix[i], multiplyRow(adMatrix, row, adMatrix[i][column])) ;
			}
//			printMatrix2(adMatrix);	    //VERY IMPORTANT !!!!! SHOULD NOT BE IN THE FINAL VERSION !!!! ONLY FOR TESTING !!!
		row = row - 1;
		column = column - 1;
		}
	}  	
	
   
   
	//solves a system of linear equations using the following algorithm
	//for each column i
	//find row with non-zero value on column i - swap rows so that this is row i
	//make adMatrix[i][i] into 1
	//make all other rows at column i into 0
	
	public static double[] solveEquations(double[][] adMatrix){
		if (!matrixRowsSameLength(adMatrix)){							//checks that the Matrix rows are in the same length , if not fills the missing cells with zeros
			adMatrix = matrixRowEqualizer(adMatrix);					//so that all the matrix rows would be in the same length.
		}
		double [] solution = new double [adMatrix[0].length - 1];
		int[] zeroColumns;
		boolean none = false;
		zeroColumns = uperTraingularMatrix2(adMatrix);
		none = noSolution(adMatrix);
		if(!none){
			dirugMatrix(adMatrix);
			int i = 0;
			int j = 0;
			while (i < adMatrix.length && j < adMatrix[i].length - 1){
				if (zeroColumns[j] != 1){
					solution[j] = adMatrix[i][adMatrix[i].length - 1];
					i = i + 1;
					j = j + 1;
				}else{
					solution[j] = 0;
					j = j + 1;
					}
			   }	
		}else{
			solution = null;
			}
		return solution;
 }



	
	
	//The function noSolution checks the Linear Equations to see if there is a row that is all zeros,
	//except the last number thus pointing out that there is no solution to the Linear Equations
	//Returns true if such row exists, else false	
	
	
	public static boolean noSolution(double[][] adMatrix){
		boolean ans=false;
		int lastRow=adMatrix.length-1;
		int lastColumn=adMatrix[lastRow].length-2;
		if(adMatrix[lastRow][lastColumn]==0 && adMatrix[lastRow][lastColumn+1]!=0){
			ans=true;	
		} 
		return ans;	
		} 
 }
	
	
	
	
	
	
	
	
